package 二分查找.easy;

/**
 * 1. 问题描述
 *      统计一个数字在排序数组中出现的次数。
 *
 * 2. 算法分析
 *      对于有重复元素的数组进行二分查找我们需要额外注意，因为我们找到的位置未必是目标元素第一次出现的位置
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 剑指Offer53I在排序数组中查找数字 {
    public static void main(String[] args) {

    }

    // 双指针法
    public static int search(int[] nums,int target) {
        // 定义双指针
        int left = 0; // 最终指向目标元素第一次出现的位置
        int right = nums.length-1; // 最终指向目标元素最后一次的位置
        // 头尾扫描
        while(left<=right) {
            if(nums[left]==target&&nums[right]==target) {
                return right-left+1;
            }
            if(nums[left] < target) left++; // 移动
            if(nums[right] > target) right--; // 移动
        }
        return 0; // 目标元素没有出现，直接返回0
    }

    /**
     * 二分递归实现
     * @param nums
     * @param target
     * @return
     */
    public static int search1(int[] nums, int target) {
        int ans = 0;
        helper(nums,target,0,nums.length-1,ans);
        return ans;
    }

    // 二分递归函数
    public static void helper(int[] nums,int target,int left,int right,int ans) {
        if (left < right) {
            int mid = left + (right-left) / 2;
            if (nums[mid] == target) {
                ans++;
                helper(nums,target,mid+1,right,ans);
                helper(nums,target,left,mid-1,ans);
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    // 线性扫描找到目标元素第一次出现的位置，然后从这里开始扫描计数即可
    public static int search2(int[] nums, int target) {
        if(nums.length == 0) {return 0;}
        int pos = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == target) {
                pos = i;
                break;
            }
            if(i == nums.length-1) {return 0;}
        }
        // 此时pos指向target第一次出现的位置
        int count = 1;
        for(int i = pos+1; i < nums.length; i++) {
            if(nums[i] == target) {count++;}
        }
        return count;
    }
}
